翻訳と辞書 Words near each other ・ Maximus of Ephesus ・ Maximus of Hispania ・ Maximus of Jerusalem ・ Maximus of Moesia ・ Maximus of Naples ・ Maximus of Pavia ・ Maximus of Rome ・ Maximus of Salzburg ・ Maximus of Turin ・ Maximus of Tyre ・ Maximus of Évreux ・ Maximum common edge subgraph problem ・ Maximum common subgraph isomorphism problem ・ Maximum Contaminant Level ・ Maximum Conviction ・ Maximum coverage problem ・ Maximum cut ・ Maximum Darkness ・ Maximum demand indicator ・ Maximum density ・ Maximum Destruction ・ Maximum Diner ・ Maximum disjoint set ・ Maximum Downside Exposure (MDE) ・ Maximum Drive ・ Maximum elevation figure ・ Maximum engineering data rate ・ Maximum entropy ・ Maximum entropy probability distribution ・ Maximum entropy spectral estimation Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Maximum coverage problem ： ウィキペディア英語版 Maximum coverage problem The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number $k$. The sets may have some elements in common. You must select at most $k$ of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size. Formally, (unweighted) Maximum Coverage : Instance: A number $k$ and a collection of sets $S\; =\; S\_1,\; S\_2,\; \backslash ldots,\; S\_m$. : Objective: Find a subset $S^\; \backslash subseteq\; S$ of sets, such that $\backslash left|\; S^\; \backslash right|\; \backslash leq\; k$ and the number of covered elements $\backslash left|\; \backslash bigcup\_\; \backslash right|$ is maximized. The maximum coverage problem is NP-hard, and cannot be approximated within $1\; -\; \backslash frac\; +\; o(1)\; \backslash approx\; 0.632$ under standard assumptions. This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for maximization of submodular functions with a cardinality constraint.〔 G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294〕 ==ILP formulation== The maximum coverage problem can be formulated as the following integer linear program. \leq k || (no more than $k$ sets are selected) |- | || $\backslash sum\_\; x\_i\; \backslash geq\; y\_j$ || (if $y\_j\; >\; 0$ then at least one set $e\_j\; \backslash in\; S\_i$ is selected) |- | || $y\_j\; \backslash in\; \backslash$ || (if $y\_j=1$ then $e\_j$ is covered) |- | || $x\_i\; \backslash in\; \backslash$ || (if $x\_i=1$ then $S\_i$ is selected for the cover) |} 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Maximum coverage problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.